#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
	# @param head, a ListNode
	# @return nothing
	def reorderList(self, head):
		if head is None:
			return head
		size = 0
		p = head
		while p is not None:
			p = p.next
			size += 1
		if size <= 2:
			return
		mid = (size+1) / 2 -1
		MID = self.__getNode(mid, head)
		
		# reverse
		reList = MID.next
		curr = MID
		backFirst = reList
		for i in xrange(size / 2):
			curr = reList
			reList = reList.next
			curr.next = MID.next
			MID.next = curr
		backFirst.next = None

		# insert
		BackList = MID.next
		MID.next = None
		toInsert = head
		for i in xrange(size / 2):
			curr = BackList
			BackList = BackList.next
			curr.next = toInsert.next
			toInsert.next = curr
			toInsert = toInsert.next.next

	def __getNode(self, ind, head):
		p = head
		for i in xrange(ind):
			p = p.next
		return p

if __name__ == '__main__':
    h = ListNode(1)
    it = h
    for i in []:
        it.next = ListNode(i)
        it = it.next

    so = Solution()
    so.reorderList(h)
    it2 = h
    while it2 is not None:
        print it2.val
        it2 = it2.next
